# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

import collections
class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        node = root
        if not node:
            return []
        stack = collections.deque()
        out = collections.defaultdict(list)
        id_dict = {}
        index = 0
        min_index = 0
        max_index = 0
        out[index].append(node.val)
        id_dict[node] = index
        while stack:
            node = stack.popleft()
            if node.left:
                stack.append(node.left)
                next_index =id_dict[node] - 1
                min_index = min(min_index, next_index)
                out[next_index].append(node.left.val)
                id_dict[node.left] = next_index
            if node.right:
                stack.append(node.right)
                next_index =id_dict[node] + 1
                max_index = max(max_index, next_index)
                out[next_index].append(node.right.val)
                id_dict[node.right] = next_index
        return_out = []
        for id in range(min_index, max_index + 1):
            return_out.append(out[id])
        return return_out



